%~ http://en.wikipedia.org/wiki/Jordan_normal_form
%~ http://en.wikipedia.org/wiki/Cholesky_factorization

\begin{section}{Mini-resumen para el segundo parcial}
%~ \item $(AB)_{ij} = \sum_{k=1}^{n} a_{ik} b _{kj}$
\begin{subsection}{Propiedades (Teórica)}
Sean $A, B \in R^{nxm}$
\begin{enumerate}
	\item Si $A$ es simétrica y tiene factorización $LU$ $\rightarrow$ su factorización es también simétrica y $A = L.D.L^t$ donde $D$ es una matríz diagonal.
	
	\item Si $A$ es simétrica definida positiva $\rightarrow$ todas sus submatrices principales son no singulares. \\
		Corolario: Si $A$ es simétrica definida positiva $\rightarrow$ $A$ tiene factorización $LU$ y $A = L.D.L^t$ \\
		Corolario: Si $A$ es simétrica definida positiva $\rightarrow$ $A = L.D.L^t$ con $d_{ii} > 0$ (Factorización de Cholesky).
		
	\item Si $A$ es estrictamente diagonal dominante $\rightarrow$ $A$ es no singular.
	
	\item Si $A$ es estrictamente diagonal dominante $\rightarrow$ todas las submatrices principales de $A$ son estrictamente diagonal dominantes. \\
		Corolario: Si $A$ es estrictamente diagonal dominante $\rightarrow$ tiene factorización $LU$.
		
	\item Las matrices de Givens son ortogonales.
	
	\item Sean $x, y \in R^n,$ tales que $||x||_2 = ||y||_2$ $\rightarrow$ $\exists$ una reflexión $P$ tal que $Px = y$ \\
	$($Puede utilizarse una matriz de reflexión de Householder con $\displaystyle u = \frac{x-y}{||x-y||_2} )$
	
	\item Si $A$ es no singular $\rightarrow$ $\exists!$ $Q, R $ tales que $Q$ es ortogonal, y $R$ es triangular superior con $r_{ii} > 0.$ \\
	(Es decir la descomposición $QR$ es única.)
	
	\item Sea $||\bullet||$ una norma matricial consistente, entonces $\rho(A) \leq ||A||$.
	
	\item $A$ es convergente $\leftrightarrow$ $\rho(A) < 1.$
	
	\item $\rho(A) < 1 \rightarrow I-A$ es no singular y $\displaystyle \sum_{k=0}^{\infty} A^k = (I-A)^{-1}.$
	
	\item Sea el sistema de ecuaciones $x = Tx + c \rightarrow$ la sucesión $x^{(k)} = x^{(k-1)}T + c$ converge a la solución del sistema 
	$\leftrightarrow$ $\rho(T) < 1,$ independientemente de la elección de $x^{(0)}$ (valor inicial).

	\item Si $A$ es estrictamente diagonal dominante $\rightarrow$ el método de Jacobi converge ($\rho(D^{-1}(L+U)) < 1$).

	\item Si $A$ es estrictamente diagonal dominante $\rightarrow$ el método de Gauss-Seidel converge ($\rho((D-L)^{-1}U) < 1$).
	
	\item Sea $||\bullet||$ una norma matricial consistente, si $||T|| < 1 \rightarrow $ la sucesión $x^{(k)} = x^{(k-1)}T + c$ converge a la solución del sistema $x = Tx + c$ y vale que:		
	\begin{enumerate}
		\item $\displaystyle ||x-x^{(k)}|| \leq {||T||}^k.||x^{(0)} - x||$
		\item $\displaystyle ||x-x^{(k)}|| \leq \frac{{||T||}^k}{1-||T||} .||x^{(1)} - x^{(0)}||$
	\end{enumerate}	
	
	\item Dadas $d^{(0)}, ..., d^{(n-1)} \in R^n$ direcciones $A$-conjugadas normalizadas, y un punto inicial $x^{(0)},$ entonces el método del gradiente encuentra la solución del sistema $Ax = b$ en $n$ pasos, es decir $Ax^{(n)} = b.$
	
	\item El polinomio interpolador de Lagrange es único.
	
	\item Sean $x_0, \dots, x_{n} \in [a,b],$ $f \in C^{n+1}$ en $[a, b]$ $\rightarrow$ $\forall x \in [a,b]$ $\exists$ $y$ tal que
	\\$f (n) = \displaystyle P(x) + E(x)$ donde $E(x) = \displaystyle \frac{\displaystyle f^{n+1}(y)}{(n+1)!} .\prod_{i=0}^n (x-x_i)$ es el error que se comete.	
	
	\item Sean $x_0, \dots, x_n \in R^n,$ puntos de interpolación $\rightarrow$ el polinomio interpolador de Lagrange es
	\\$P (x) = \displaystyle \frac{\displaystyle (x-x_j)P_{0,\dots,j-1,j+1,\dots,n} - (x-x_i)P_{0,\dots,i-1,i+1,\dots,n}}{x_i - x_j}$.	
	
	\item Sean $x_0, \dots, x_n \in R^n,$ puntos de interpolación $\rightarrow$ el polinomio interpolador de Lagrange es
	\\$P (x) = \displaystyle f(x_0) + \sum_{i=1}^n f[x_0,\dots,x_i] \prod_{k=0}^{i-1} (x-x_k)$.
	
	%~ \item
	
\end{enumerate}
\end{subsection}

\begin{subsection}{Propiedades (Prácticas)}
Sean $A, B \in R^{nxm}, Q \in R^{nxn}, x \in R^n$
\begin{enumerate}
	\item $AA^t$ y $A^tA$ son simétricas. Si $A$ es cuadrada, $A + A^t$ es simétrica y $A - A^t$ es antisimétrica.
	\item Si $A$ es cuadrada, entonces es expresable de forma única como $A = S + T$ donde $S$ es simétrica y $T$ es antisimétrica.
	\item Si $A$ y $B$ son simétricas, entonces $A + B$ y $A - B$ son simétricas. Si además $AB = BA$, entonces $AB$ es simétrica.
	\item $A$ y $B$ cuadradas. $A$ es definida positiva y $B$ es no singular $\leftrightarrow$ $BAB^t$ es definida positiva.
	\item $A$ y $B$ ortogonales, entonces $AB$ es ortogonal.
	\item $Q$ ortogonal, entonces $|\mbox{det}(Q)| = 1$ y $||Qx||_2 = ||x||_2.$ \\
		Corolario: $||Q||_2 = 1.$ \\ 
		Corolario: $K_2(Q) = 1.$ 
	%~ \item 	
	\item La matríz de reflexión de Householder $P_{u}$ es simétrica y ortogonal.
\end{enumerate}

\end{subsection}

\begin{subsection}{Definiciones}
Sea $A, T \in R^{nxn}, x, b, c \in R^n$
\begin{enumerate}
%~ \item
\item $A$ se dice antisimétrica si $A = - A^t$.

\item $A \in R^{nxn}$ simétrica, si vale que: 
	\begin{enumerate}
		\item $x^t.A.x > 0$ $\forall x \in R^{n}, x \neq 0$, entonces A es definida positiva.
		\item $x^t.A.x \geq 0$ $\forall x \in R^{n}, x \neq 0$, entonces A es semidefinida positiva.
		\item $x^t.A.x < 0$ $\forall x \in R^{n}, x \neq 0$, entonces A es definida negativa.
		\item $x^t.A.x \leq 0$ $\forall x \in R^{n}, x \neq 0$, entonces A es semidefinida negativa.
	\end{enumerate}

\item $A$ es ortogonal $\leftrightarrow$ $A^{-1} = A^{t}$ $\leftrightarrow$ las columnas de $A$ forman una base ortonormal 
$\leftrightarrow$ las filas de $A$ forman una base ortonormal $\leftrightarrow$ 
\\$<\mbox{columna}_i(A), \mbox{columna}_j(A)>$ $=$ $<\mbox{fila}_i(A), \mbox{fila}_j(A)>$ $=$
$\delta_{ij} = 1 \mbox{ si } i = j, 0 \mbox{ si } i \neq j$.

\item La descomposición $QR$ de $A$ es $A = QR$ donde $Q$ es una matríz ortogonal y $R$ es una matríz triangular superior.

\item Se define la matŕiz de rotación de Givens $G_{1k}$ como la matríz que realiza la rotación entre el plano $1$ y el plano $K$, suponiendo que el ángulo entre ellos es $\theta_{1j}$ en sentido horario. 
%~ \paragraph{}
\begin{center}
$\displaystyle G_{1k} = \begin{pmatrix} \cos{\theta_{1j}} & 0 & \ldots & 0 & \sin{\theta_{1j}} & 0 & \ldots & 0 
\\ 0 & 1 & 0 & 0 & \ldots & \ldots & \ldots & 0 
\\ \vdots & 0 & \ddots & 0 & \ldots & \ldots & \ldots & 0
\\ 0 & 0 & \ldots & 1 & 0 & \ldots & \ldots & 0 
\\ -\sin{\theta_{1j}} & 0 & \ldots & 0 & \cos{\theta_{1j}} & 0 & \ldots & 0 
\\ 0 & 0 & \ldots & 0 & 0 & 1 & \ldots & 0
\\ \vdots & 0 & \ldots & \ldots & \ldots & 0 & \ddots & 0
\\ 0 & 0 & \ldots & \ldots & \ldots & 0 & 0 & 1 \end{pmatrix} $
\end{center}

%~ ${G_{1k}}_{ij} = {I_n}_$
\item Dado $u \in R^n,$ $||u||_2 = 1$, se define la matríz de reflexión de Householder $P_{u}$ como $P_{u} = I - 2uu^t$. Esta transformación cumple que $P_{u}u = u$ y dado $v \in R^n,$ $<u,v> = 0$, $P_{u}v = 0.$
%~ \paragraph{}
\begin{center}
$\displaystyle P_{u} = \begin{pmatrix} 
   1-2{u_{1}}^2 & -2 u_{1}u_{2} & \ldots & -2 u_{1}u_{n} 
\\ -2 u_{1}u_{2} & 1-2{u_{2}}^2 & \ldots & -2 u_{2}u_{n}
\\ \vdots & \ldots & \ddots & \ldots
\\ -2 u_{1}u_{n} & -2 u_{2}u_{n} & \ldots & 1-2{u_{n}}^2 \end{pmatrix} $
\end{center}

\item $\lambda$ es autovalor de $A$ si $\exists$ $x \neq 0$ tal que $Ax = \lambda x$. En tal caso $x$ es un autovector.

\item Se define el polinomio característico de $A$ como $P(\lambda) = \mbox{det}(I - \lambda A)$ o como $P(\lambda) = \mbox{det}(A - \lambda I)$. 
Las raíces de $P(\lambda)$ son los autovalores de $A$.

\item Sean $\lambda_1, ... \lambda_n$ los autovalores de $A$, se define el radio espectral de $A$ como $\displaystyle \rho(A) = \max_{1\leq i \leq n} |\lambda_i|.$ 
%~ = \max\{|\lambda_i|, \lambda_i \mbox{ es autovalor de } A\}$.

\item $A$ es convergente si $ \displaystyle \lim_{k \rightarrow \infty} (A^k)_{ij} = 0$, es decir $\displaystyle \lim_{k \rightarrow \infty} A^k = 0$ (matríz nula).

\item Sea $A$ simétrica definida positiva, $u_1, ..., u_n \in R^n$ son direcciones $A$-conjugadas si vale que ${u_i}^t A u_j = 0$ $\forall i \neq j,$ si además se cumple que 
${u_i}^t A u_i = 1$ $\forall i$, entonces están normalizadas.

\item Sean $x_0, \dots, x_n \in R^n,$ y $y_1, \dots, y_n \in R^n$ tales que $F(x_i) = y_i$ $\forall i$ para alguna función $f: R \shortrightarrow R$. 
$P: R \shortrightarrow R$ es polinomio interpolador de $f$, y $x_0, \dots, x_n$ son puntos de interpolación $\leftrightarrow$ $P(x_i) = y_i$ $\forall i$.

\item Dados $x_0, \dots, x_n \in R^n,$ puntos de interpolación, se define el polinomio interpolador de Lagrange 
\\$P: R \shortrightarrow R$ como $\displaystyle P (x) = \sum_{k=0}^{n} y_k.L_{n,k}(x),$ donde 
$L_{n,k}: R \shortrightarrow R$ $\displaystyle L_{n,k} (x) = \prod_{i=0, i\neq k}^{n} \frac{x - x_i}{x_k - x_i}$.\\
Notación: $P_{1, \dots, n}$ es el polinomio interpolador en $x_1, \dots, x_n.$

\item Se define la diferencia dividida de orden $k$ en los puntos $x_i, x_{i+1}, \dots, x_{i+k}$ como\\
$\displaystyle f[x_i, \dots, x_{i+k}] = \frac{f[x_{i+1},\dots,x_{i+k}] - f[x_{i},\dots,x_{i+k-1}]}{x_{i+k}-x_i}$ con $f[x_i] = f(x_i).$

\item $S(x)$ es spline si
	\begin{enumerate}
		\item $S(x)$ es un polinomio de grado $3$ en $[x_j, x_{j+1}]$ $\forall j,$ $j=0,\dots,n-1$
			\begin{itemize}
				\item $S_j(x) = a_j{(x-x_j)}^3 + b_j{(x-x_j)}^2 + c_j{(x-x_j)} + d_j$
				\item ${S'}_j(x) = 3.a_j{(x-x_j)}^2 + 2.b_j{(x-x_j)} + c_j$
				\item ${S''}_j(x) = 6.a_j{(x-x_j)} + 2.b_j$
			\end{itemize}	
		\item $S(x_j) = f(x_j)$ $\forall j,$ $j=0,\dots,n$		
		\item $S_{j+1}(x_{j+1}) = S_j(x_{j+1})$ $\forall j,$ $j=0,\dots,n-2$ (continuidad).
		\item $S'_{j+1}(x_{j+1}) = S'_j(x_{j+1})$ $\forall j,$ $j=0,\dots,n-2$ (derivadas iguales de ambos lados).
		\item $S''_{j+1}(x_{j+1}) = S''_j(x_{j+1})$ $\forall j,$ $j=0,\dots,n-2$ (concavidades iguales de ambos lados).		
	\end{enumerate}
	Se necesitan dos condiciones más para poder resolver de forma única el sistema de ecuaciones y encontrar los valores de los coeficientes de los polinomios.
	Dos opciones son:
	\begin{itemize}
		\item Frontera Libre: $S''(x_{0}) = 0$ y $S''(x_{n}) = 0$ (Spline Natural).
		\item Frontera Sujeta: $S'(x_{0}) = f'(x_0)$ y $S'(x_{n}) = f'(x_n)$ (Spline Sujeto).
	\end{itemize}
	con estas dos opciones se obtiene un sistema con una matríz estrictamente diagonal dominante, lo que asegura que la solución existe y es única.
%~ \item 
	%~ \par \noindent
	
\end{enumerate}
\end{subsection}

\begin{subsection}{Factorización de Cholesky}
\par \noindent
Dada $A$ simétrica definida positiva, encuentra la factorización $L.D.L^t$ de $A$ en ${n^3}/3$ operaciones (dos veces más rápidamente que en la factorización $LU$ que se hace en $2{n^3}/3$ operaciones).

\begin{algorithm}[H]
\caption{Cholesky($A \in R^{nxn}$)}
\BlankLine
%~ \textsl{\{ Punteros a las matrices. \}}\\
$\displaystyle l_{11} = \sqrt{a_{11}}$
\BlankLine
\For{($j = 2$; $j \leq n$; $j++$)}
{
	\BlankLine
	$\displaystyle l_{j1} = \frac{a_{j1}}{a_{11}}$
	\BlankLine
}
\BlankLine
\For{($i = 2$; $i < n$; $i++$)}
{
	\BlankLine
	$\displaystyle l_{ii} = \sqrt{a_{ii} - \sum_{k = 1}^{i-1} {l_{ik}}^2}$
	\BlankLine
	\For{($j = i+1$; $j \leq n$; $j++$)}
	{
		\BlankLine
		$\displaystyle l_{ji} = \frac{a_{j1} - \displaystyle \sum_{k = 1}^{i-1} l_{jk} l_{ik}} {a_{ii}}$
		\BlankLine
	}
	\BlankLine
}
\BlankLine
$\displaystyle l_{nn} = \sqrt{a_{nn} - \sum_{k = 1}^{n-1} {l_{nk}}^2}$ 
\end{algorithm}
\end{subsection}

\newpage
\begin{subsection}{Factorización QR}
\par \noindent
Se busca triangular $A$ multiplicando a izquierda por matrices ortogonales, obteniendo $Q^tA = R \shortrightarrow A = QR.$
%~ \par \noindent
%~ Ambos métodos se realizan en forma recursiva, para triangular $A$ primero se obtienen ceros debajo del primer elemento de la primera fila y luego se aplica el método sobre la submatríz que resulta de eliminar la primera fila y la primera columna. Para no afectar el resultado ya obtenido, las siguientes matrices de rotación y reflexión que se utilicen se llenan con la identidad.
%~ \begin{subsubsection}{Método de Rotaciones}
%~ \par
%~ Se triangula A multiplicando a izquierda por matrices de Givens, en el primer paso, se ...
%~ \end{subsubsection}
$W, W^{(i)}, B^{(i)}  \in R^{nxn}$,  ${B'}^{(i)} , {W'}^{(i)} \in R^{(n-i) x (n-i)}$\\
\begin{algorithm}[H]
\caption{Rotaciones($A \in R^{nxn}$)}
\BlankLine
$W= I_n$\\
$B^{(1)} = A$\\
${B'}^{(1)} = A$
\BlankLine
\For{($i = 1$; $i < n$; $i++$)}
{
	\BlankLine
	$W^{(i)} = I_n$\\
	${W'}^{(i)} = I_{n-i+1}$
	\BlankLine
	\For{($k = i+1$; $k < n$; $k++$)}
	{
		%~ \BlankLine
		%~ $\displaystyle \theta_{ij} = $ ángulo entre ${B'}^{(i)}_{1k}$ y $0$
		\BlankLine
		$\displaystyle norma = \sqrt{{{B'}^{(i)}_{11}}^2 + {{B'}^{(i)}_{1k}}^2}$
		\BlankLine
		$\displaystyle \cos(\theta_{ij}) = \frac{{B'}^{(i)}_{1k}}{norma}$
		\BlankLine
		$\displaystyle \sin(\theta_{ij}) = \frac{{B'}^{(i)}_{11}}{norma}$
		\BlankLine
		$\displaystyle {W}_{ij} = G_{1k}$ para la matríz ${B'}^{(i)}$ usando $\sin(\theta_{ij})$ y $\cos(\theta_{ij}).$
		\BlankLine
		${W'}^{(i)} = W_{ij}.{W'}^{(i)}$
	}
	\BlankLine
	$\displaystyle {W}^{(i)} = \begin{pmatrix} I_{i-1} & 0 \\ 0 & {W'}^{(i)} \end{pmatrix}$	
	\BlankLine
	$\displaystyle {B'}^{(i+1)} = W^{(i)}.{B'}^{(i)}$ 
	\BlankLine
	$\displaystyle {B}^{(i+1)} = {B'}^{(i+1)}$ sin las primeras $i$ filas y columnas.
	\BlankLine
	$W = W^{(i)}.W$
	\BlankLine
}
%~ \BlankLine
$Q = W^t$\\
$R = {B'}^{(n)}$
\end{algorithm}

%~ $\displaystyle x_1 = \mbox{columna}_1 (A)$, $\displaystyle y_1 = (||x_1||_2, 0, \dots, 0),$ como $\displaystyle ||x_1||_2 = ||y_1||_2, \exists P_1$ reflexión tal que $P_1x = y$, logrando de esta manera ($P_1A$) obtener ceros debajo de la diagonal de $A$ para la primera fila.

\begin{algorithm}[H]
\caption{Reflexiones($A \in R^{nxn}$)}
\BlankLine
$W= I_n$\\
$B^{(1)} = A$\\
${B'}^{(1)} = A$
\BlankLine
\For{($i = 1$; $i < n$; $i++$)}
{
	\BlankLine
	$\displaystyle x_i = \mbox{columna}_1 (B^{(i)})$
	\BlankLine
	$\displaystyle y_i = (||x_i||_2, 0, \dots, 0)$
	\BlankLine
	$\displaystyle u_i = \frac{x-y}{||x-y||_2}$
	\BlankLine
	$\displaystyle P^{(i)} = P_u$ Matríz de Reflexión de Householder.
	\BlankLine
	$\displaystyle W^{(i)} = \begin{pmatrix} I_{i-1} & 0 \\ 0 & P^{(i)} \end{pmatrix}$
	\BlankLine
	$\displaystyle {B'}^{(i+1)} = W^{(i)}.{B'}^{(i)}$ 
	\BlankLine
	$\displaystyle {B}^{(i+1)} = {B'}^{(i+1)}$ sin las primeras $i$ filas y columnas.
	\BlankLine
	$W = W^{(i)}.W$
	\BlankLine
}
\BlankLine
$Q = W^t$\\
$R = {B'}^{(n)}$
\end{algorithm}

\end{subsection}

\newpage
\begin{subsection}{Métodos Iterativos Para Sistemas Lineales}
\par \noindent
Sea el sistema de ecuaciones $Ax = b$ y $x^{(0)} = ({x_1}^{(0)}, \dots, {x_n}^{(0)}) \in R^n$ inicial.

\begin{subsubsection}{Algoritmos}
\begin{algorithm}[H]
\caption{Jacobi($A \in R^{nxn}, b, x^{(0)} \in R^n$)}
\BlankLine
\For{($k = 1$; $k \leq n$; $k++$)}
{
	\For{($i = 1$; $i \leq n$; $i++$)}
	{
		\BlankLine
		$\displaystyle {x_{i}}^{(k)} = \frac{b_i - \displaystyle \sum_{j=1, j\neq i}^{n} a_{ij}.{x_j}^{(k-1)} }{a_{ii}}$
	}
}
Con $a_{ii} \neq 0$ $\forall i.$
\end{algorithm}

\begin{algorithm}[H]
\caption{Gauss-Seidel($A \in R^{nxn}, b, x^{(0)} \in R^n$)}
\BlankLine
\For{($k = 1$; $k \leq n$; $k++$)}
{
	\For{($i = 1$; $i \leq n$; $i++$)}
	{
		\BlankLine
		$\displaystyle {x_{i}}^{(k)} = 
		\frac{b_i - \displaystyle \sum_{j=1}^{i-1} a_{ij}.{x_j}^{(k)} - \displaystyle \sum_{j=i+1}^{n} a_{ij}.{x_j}^{(k-1)}}{a_{ii}}$
	}
}
Con $a_{ii} \neq 0$ $\forall i.$
\end{algorithm}
\end{subsubsection}

\begin{subsubsection}{Forma Matricial}
$A$ se expresa como $A = D-L-U$, donde \paragraph{}
$\displaystyle D = \begin{pmatrix} a_{11} & 0 & \ldots & 0\\ 0 & a_{22} & \ldots & 0 \\ \vdots & 0 & \ddots & 0 \\ 0 & 0 & \ldots & a_{nn} \end{pmatrix} $ 
$\displaystyle L = \begin{pmatrix} 0 & 0 & \ldots & 0\\ -a_{21} & 0 & \ldots & 0 \\ \vdots & \ddots & 0 & 0\\ -a_{n1} & \ldots & -a_{n n-1} & 0 \end{pmatrix} $ 
$\displaystyle U = \begin{pmatrix} 0 & -a_{12} & \ldots & -a_{1n} \\ 0 & 0 & \ddots & \vdots \\ 0 & \ldots & 0 & -a_{n-1 n} \\ 0 & \ldots & 0 & 0 \end{pmatrix} $ 
\paragraph{} \noindent
definendo las matrices $T$ y las constantes $C$ para los métodos iterativos de Jacobi y de Gauss-Seidel. 
	\begin{itemize}
		\item \textbf{Jacobi} $T = D^{-1}(L+U)$ y $c = D^{-1}b$ 
		\item \textbf{Gauss-Seidel}	$T = (D-L)^{-1}U$ y $c = (D-L)^{-1}b$
	\end{itemize}
	
\par \noindent
En ambos métodos se utiliza la sucesión $x^{(k)} = x^{(k-1)}T + c$ para resolver el sistema (si es que el método converge).
\end{subsubsection}

\end{subsection}


\newpage
\begin{subsection}{Método del Gradiente Conjugado}
\par \noindent
Sea $A$ simétrica definida positiva, y el sistema de ecuaciones $Ax = b.$
%~ Sea $Q: R \shortrightarrow R,$ $\displaystyle R(x) = x^tAx - 2x^tb = x_1 \sum_{j=1}^{n} a_{1j} x_j + \dots + x_n \sum_{j=1}^{n} a_{nj} x_j - 2x_1b_1 - \dots - 2x_nb_n$\\
%~ \par \noindent
%~ $\nabla Q(x) = 2(Ax-b)$
%~ $H Q(x) = 2A$ $> 0$ por ser $A$ definida positiva. \\
%~ \par \noindent
%~ $x \in R$ tal que minimiza $Q$ es punto crítico de la función ($Q$ es una parábola positiva) y por lo tanto resuelve el sistema $Ax = b.$\\
%~ \par \noindent
%~ $Q(x + \alpha d) = {\alpha}^2 d^t A d + 2 \alpha d^t (Ax-b) + x^tAx - 2x^t b$ \\
%~ \par \noindent
%~ $\displaystyle \frac{\partial Q(x + \alpha d)}{\partial \alpha} = 2\alpha d^t A d + d^t(Ax-b) = 0 \rightarrow \alpha = \frac{d^t(b-Ax)}{d^tAd}$
\begin{subsubsection}{Si se tienen las direcciones}
\begin{algorithm}[H]
\caption{Algoritmo de Direcciones($A \in R^{nxn}, x^{(0)} \in R$ inicial, $b \in R^n$, $d^{(0)}, ..., d^{(n-1)} \in R^n$ direcciones, $N \in R$ límite)}
\BlankLine
\For{($j = 1$; $j \leq N$; $j++$)}
{
	\BlankLine
	$\displaystyle {\alpha}^{(k-1)} = \frac{{d^{(k-1)}}^t(b-Ax^{(k-1)})}{{d^{(k-1)}}^tA.d^{(k-1)}}$ 
	\BlankLine
	$\displaystyle x^{(k)} = x^{(k-1)} + {\alpha}^{(k-1)} d^{(k-1)}$
	\BlankLine
}
\end{algorithm}
\end{subsubsection}

\par \noindent
En el método del gradiente conjugado, las direcciones son $A$-conjugadas, y el límite es $n$.

\begin{subsubsection}{Si no se tienen las direcciones}
\par \noindent
El siguiente algoritmo genera direcciones $A$-conjugadas a medida que las va necesitando en cada paso del algoritmo.\\

\begin{algorithm}[H]
\caption{($A \in R^{nxn}, x^{(0)} \in R$ inicial, $b \in R^n$)}
\BlankLine
$r^{(0)} = b - Ax^{(0)}$\\
$d^{(0)} = -r^{(0)}$
\BlankLine
\For{($j = 1$; $j \leq N$; $j++$)}
{
	\BlankLine
	$\displaystyle {\alpha}^{(k-1)} = \frac{{d^{(k-1)}}^t(b-Ax^{(k-1)})}{{d^{(k-1)}}^tA.d^{(k-1)}}$ 
	\BlankLine
	$\displaystyle x^{(k)} = x^{(k-1)} + {\alpha}^{(k-1)} d^{(k-1)}$
	\BlankLine
	$\displaystyle \beta_k = \frac{ {r^{(k)}}^t A.d^{(k-1)}}{{d^{(k-1)}}^tA.d^{(k-1)}}$
	\BlankLine
	$r^{(k)} = b - Ax^{(k)}$
	\BlankLine
	$d^{(k)} = -r^{(k)} + \beta_{k}.d^{(k-1)}$
	\BlankLine
}
\end{algorithm}
\end{subsubsection}

\end{subsection} 

\end{section}
